package com.frx.datastruct.chaptereight;

import java.util.ArrayList;
import java.util.Random;

/**
 * Created by xurenfeng on 2019/3/6.
 * 测试将一个数组转换为最大堆的时间复杂度
 */
public class HeapifyTest {

    public static double testHeap(Integer[] arrData,boolean isHeapify){
        long startTime = System.nanoTime();
        MaxHeap<Integer> maxHeap;
        if (isHeapify){
            maxHeap = new MaxHeap<>(arrData);
        } else {
            maxHeap = new MaxHeap<>();
            for (int i = 0;i<arrData.length;i++){
                maxHeap.add(arrData[i]);
            }
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i<maxHeap.getSize();i++){
            list.add(maxHeap.extractMax());
        }
        for (int i = 1 ; i<list.size();i++){
            if (list.get(i-1) < list.get(i)){
                throw new IllegalArgumentException("error!");
            }
        }
        System.out.println("testHeap completed");

        long endTime = System.nanoTime();

        return (endTime - startTime)/1000000000.0;
    }
    public static void main(String[] args){

        int n = 1000000;
        Random random = new Random();
        Integer[] testData = new Integer[n];
        for (int i=0;i<testData.length;i++){
            testData[i] = random.nextInt(Integer.MAX_VALUE);
        }

        double time1 = testHeap(testData,false);
        System.out.println("without heapify time:" + time1);
        double time2 = testHeap(testData,true);
        System.out.println("with heapify time:" + time2);

    }

}
